# -*- coding: utf-8 -*-

"""剑指 Offer II 098. 路径的数目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

示例 1：
输入：m = 3, n = 7
输出：28

示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：
输入：m = 7, n = 3
输出：28

示例 4：
输入：m = 3, n = 3
输出：6

提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109"""


class Solution:
    """动态规划：
    f(i, j) = f(i-1, j)+f(i, j-1)
    f(0, 0) = 1
    
    行列头部添加哨兵
    
    这道题看似简单，其实可拓展性非常强，就是经典的两栈组合问题，可以用数学排列组合方法解决。
    可以扩展成字符串有多少种交织方法等问题"""
    def uniquePaths(self, m: int, n: int) -> int:
        m += 1
        n += 1
        dp = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                if i == 1 and j == 1:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j]+dp[i][j-1]
        return dp[i][j]


if __name__ == '__main__':
    so = Solution()
    print(so.uniquePaths(m = 3, n = 7))
    print(so.uniquePaths(m = 3, n = 2))
    print(so.uniquePaths(m = 7, n = 3))
    print(so.uniquePaths(m = 3, n = 3))
